public class Offer4 {
    boolean flag = false;
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length==0){
            return false;
        }
        dfs(matrix,target,matrix[0].length-1,0);
        return flag;
    }
    public void dfs(int[][] matrix, int target,int col,int row){
        if (!isValid(matrix,col,row)){
            return;
        }
        int val = matrix[row][col];
        if (target>val){
            dfs(matrix, target, col , row+1);
        }else if (target<val){
            dfs(matrix, target, col-1, row);
        }else {
            flag = true;
            return;
        }
    }
    public boolean isValid(int[][] matrix,int col,int row){
        if (row>=0&&row< matrix.length&&col>=0&&col<matrix[0].length){
            return true;
        }else {
            return false;
        }
    }
}
